#include <stdlib.h>
#include <stdio.h>

#include "main.h"

// root_p 指向已经被正确初始化的 BiTreeNode
// pre_order_seq 是前序遍历时得到的字符串序列，其中每个空左子节点或者空右子节点均用 # 表示
// current_index_p 是指针，所指向的值用于记录在 pre_order_seq 中等待被处理的字符的位置；第一次调用 _recur_create_tree 函数时，其值为0
// num_elements 指出 pre_order_seq 里包含的字符个数
// 本函数仅推荐使用，你可以自行设计其他辅助函数。
void _recur_create_tree(BiTreeNode * root_p, char * pre_order_seq, int * current_index_p, int num_elements) {
  // 如果current_index_p指向的值已经等于或者超过num_elements，那么程序返回（否则就会超出 pre_order_seq 提供的字符范围）

  // 把在 *current_index_p 位置上的字符 设置为 root_p 所指向的结点的数据

  // 更新 *current_index_p 使其指向下一个待扫描的字符

  // 判断是否要建立左子树
  // 如果 下一个带扫描的字符 为 #：
  //   那么不用新建左子节点（为什么？）而是让左子节点为NULL，并继续相应地更新 *current_index_p 使其指向下一个扫描的字符(从而消耗掉#字符)
  // 否则
  //   新建左子节点，并递归调用 本函数 _recur_create_tree
  

  // 判断是否要建立右子树
  // 如果 下一个带扫描的字符 为 #：
  //   那么不用新建右子节点（为什么？）而是让右子节点为NULL，并继续相应地更新 *current_index_p 使其指向下一个扫描的字符(从而消耗掉#字符)
  // 否则
  //   新建右子节点，并递归调用 本函数 _recur_create_tree
}

// 根据带有显式空子节点的先序序列，构建二叉树，将其头节点的指针存入root_pp中
// 初始传入的root_pp的值无任何意义（也即root_pp尚未被正确地初始化，也即是需要你来初始化）
// pre_order_seq 指向的字符串类似 "ABC##DE#G##F###"，其中 # 表示显式的空子节点，这一类空子节点并不需要被创建对应的struct Node或者BiTreeNode

void create_tree(BiTreeNode** root_pp, char* pre_order_seq, int num_elements) {
	// 初始化整棵树的根节点
	static int num_element = -1;
	num_element++;
	if (pre_order_seq[num_element] != '\0' && pre_order_seq[num_element] != '#') {
		(*root_pp) = (BiTreeNode*)malloc(sizeof(BiTreeNode));
		(*root_pp)->data = pre_order_seq[num_element];
		create_tree(&((*root_pp)->leftChild), pre_order_seq, num_elements);
		create_tree(&((*root_pp)->rightChild), pre_order_seq, num_elements);
	}
	else {
		(*root_pp) = 0;
	}
	
	// 使用合适的参数调用上面定义的 _recur_create_tree 函数
}


// 递归地销毁由*root指向根节点的树：释放该树所被动态分配的内存空间
void destroy(BiTreeNode** root)
{
	if ((*root) != 0) {
		destroy(&((*root)->leftChild));
		destroy(&((*root)->rightChild));
		free(*root);
	}
}

//使用visit(item)函数前序遍历二叉树t
void pre_order_traverse(BiTreeNode* t, void visit(DataType item))
{
	if (t != 0) {
		visit(t->data);
		pre_order_traverse(t->leftChild, visit);
		pre_order_traverse(t->rightChild, visit);
		
	}
	
}

//使用visit(item)函数中序遍历二叉树t
void in_order_traverse(BiTreeNode* t, void visit(DataType item))
{
	if (t != 0) {
		in_order_traverse(t->leftChild, visit);
		visit(t->data);
		in_order_traverse(t->rightChild, visit);
	}
}

//使用void visit(DateType item)函数后序遍历二叉树t
void post_order_traverse(BiTreeNode* t, void visit(DataType item))
{
	if (t != 0) {
		post_order_traverse(t->leftChild, visit);
		post_order_traverse(t->rightChild, visit);
		visit(t->data);
	}
}

// 请实现此函数
// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
BiTreeNode* search(BiTreeNode* root, DataType x)
{
	if(root == NULL) { // 如果根节点为空，则返回NULL
		return NULL;
	}
	if(root->data == x) { // 如果根节点的值等于x，则返回根节点
		return root;
	}
	BiTreeNode *find = search(root->leftChild, x); // 在左子树中查找x
	if(find == NULL) { // 如果左子树中没有找到x，则在右子树中查找x
		find = search(root->rightChild, x);
	}
	return find; // 返回查找结果
}

void visit(DataType item)
{
	printf("%c ", item);
}


int main(void)
{
	void (*p)(DataType item) = visit;
	BiTreeNode* treeNode = 0;
	char letter = 'A';
	create_tree(&treeNode, "ABC##DE#G##F###", 7);
	pre_order_traverse(treeNode, p);
	printf("%p", search(treeNode, letter));
	destroy(&treeNode);
	return 0;
}